package oj;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

//最小K个数：设计一个算法，找出数组中最小的K个数。以任意顺序返回这K个树
public class Solution_1714 {
    //1.使用java.util.PriorityQueue
//    static class IntegerReverseComparator implements Comparator<Integer>{
//        @Override
//        public int compare(Integer o1, Integer o2) {
//            return o2 - o1;
//        }
//    }
//    public int[] smallestK(int[] arr, int k) {
//        if(k == 0){
//            return new int[0];
//        }
//        //要找到最小的k个树，所以要建一个有k个数的大堆
//        //但是java.util.PriorityQueue中实现的是小堆
//        //所以这时候我们只要改变比较大小的规则就可以了
//        //定义 5 “小于” 3 , 3 “大于” 5 , 3 “等于”3
//        //Integer 有自然顺序 Comparable ，但是这个不符合我们的要求
//        //所以使用 Comparator 去实现
//        Comparator<Integer> c = new IntegerReverseComparator();
//        PriorityQueue<Integer> queue = new PriorityQueue<>(c);
//
//        //把前k个数放入堆中
//        for(int i = 0;i < k;i++){
//            queue.offer(arr[i]);
//        }
//        //用剩下的元素和堆顶元素进行比较
//        for(int i = k;i < arr.length;i++){
//            int e = arr[i];
//            int t = queue.peek();
//
//            //我们平时理解的小
//            if(e < t){
//                //先把堆顶元素删除
//                queue.poll();
//                //放入新的候选人
//                queue.offer(e);
//            }
//        }
//        int[] ans = new int[k];
//        for(int i = 0;i < k;i++){
//            ans[i] = queue.poll();
//        }
//        return ans;
//    }

    //2.用自己建立大堆，自己进行向下调整
    //向下调整
    public static void adjustDown(int[] arr,int size,int index){
        while(2 * index + 1 < size){
            int maxIdx = 2 * index + 1;
            if(maxIdx + 1 < size && arr[maxIdx + 1] > arr[maxIdx]){
                maxIdx++;
            }
            if(arr[index] >= arr[maxIdx]){
                break;
            }

            int tmp = arr[index];
            arr[index] = arr[maxIdx];
            arr[maxIdx] = tmp;

            index = maxIdx;
        }
    }
    //建大堆
    public static void createHeap(int[] arr,int size){
        for(int index = (size - 2) / 2;index >= 0;index--){
            adjustDown(arr,size,index);
        }
    }

    public int[] smallestK(int[] arr, int k){
        if(k == 0){
            return new int[0];
        }
        int[] ans = Arrays.copyOf(arr,k);   //将前k个复制到一个新的数组
        //把 ans 建成大堆
        createHeap(ans,k);

        for(int i = k;i < arr.length;i++){
            //遍历的元素比堆顶元素小，有资格成为候选
            if(arr[i] < ans[0]){
                ans[0] = arr[i];
                adjustDown(ans,k,0);
            }
        }
        return ans;
    }
}
